//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int len = INT_MAX;
//        int sum = 0;
//        for (int left = 0, right = 0, n = nums.size(); right < n; right++)
//        {
//            sum += nums[right];
//            while (sum >= target)
//            {
//                len = min(len, right - left + 1);
//                sum -= nums[left++];
//            }
//        }
//        return len == INT_MAX ? 0 : len;
//    }
//};




//class Solution {
//public:
//    int lengthOfLongestSubstring(string s) {
//        int hash[128] = { 0 };
//        int len = 0, left = 0, right = 0, n = s.size();
//        while (right < n)
//        {
//            hash[s[right]]++;
//            while (hash[s[right]] > 1)
//            {
//                hash[s[left]]--;
//                left++;
//            }
//            len = max(len, right - left + 1);
//            right++;
//        }
//        return len;
//    }
//};




//class Solution {
//public:
//    int findMaxConsecutiveOnes(vector<int>& nums) {
//        int ret = 0, len = 0;
//        for (auto x : nums)
//        {
//            if (x == 0)
//            {
//                len = 0;
//            }
//            else
//            {
//                len++;
//                ret = max(ret, len);
//            }
//        }
//        return ret;
//    }
//};



//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int ret = 0;
//        for (int left = 0, right = 0, zero = 0, n = nums.size(); right < n; right++)
//        {
//            if (nums[right] == 0) zero++;
//            while (zero > k)
//            {
//                if (nums[left++] == 0) zero--;
//            }
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};




//class Solution
//{
//public:
//	int jump(vector<int>& nums)
//	{
//		int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
//		while (left <= right)
//			if (maxPos >= n - 1) 
//			{
//				return ret;
//			}
//			for (int i = left; i <= right; i++)
//			{
//				maxPos = max(maxPos, nums[i] + i);
//			}
//			left = right + 1;
//			right = maxPos;
//			ret++;
//		}
//		return -1;
//	}
//};


//class Solution
//{
//public:
//	int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
//	{
//		int n = gas.size();
//		for (int i = 0; i < n; i++) 
//		{
//			int rest = 0;
//			int step = 0;
//			for (; step < n; step++) 
//			{
//				int index = (i + step) % n; 
//				rest = rest + gas[index] - cost[index];
//				if (rest < 0) break;
//			}
//			if (rest >= 0) return i;
//			i = i + step; 
//		}
//		return -1;
//	}
//};


class Solution
{
public:
	int monotoneIncreasingDigits(int n)
	{
		string s = to_string(n); 
		int i = 0, m = s.size();
		while (i + 1 < m && s[i] <= s[i + 1]) i++;
		if (i + 1 == m) 
			return n; 
		while (i - 1 >= 0 && s[i] == s[i - 1]) i--;
		s[i]--;
		for (int j = i + 1; j < m; j++) 
			s[j] = '9';
		return stoi(s);
	}
};